package 剑指offer;

import sun.reflect.generics.tree.Tree;

class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;
    public TreeLinkNode(int val) {
        this.val = val;
    }
}

public class Offer08_JZ57 {

    public static TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode == null) return null;
        TreeLinkNode next = null;
        if (pNode.right != null) {  // 如果该节点有右节点，则下一个结点为右子树的最左结点
            TreeLinkNode cur = pNode.right;
            while (cur.left != null) {
                cur = cur.left;
            }
            return cur;
        } else if (pNode.next != null) {
            // 如果该节点右子树为空且为父节点的左子树，则下一个结点为父节点
            // 如果该节点右子树为空且为父节点的右子树，沿着父节点找到一个结点，且此结点是他父节点的左节点，则这个结点的父节点就是下一个结点
            TreeLinkNode cur = pNode;
            TreeLinkNode parent = pNode.next;
            while (parent!=null && cur == parent.right) {
                cur = parent;
                parent = parent.next;
            }
            next = parent;
        }
        return next;
    }
}
